package Offer.offer2016;

import domain.ListNode;

//O(1)ʱ��ɾ����������Ľ��
//class ListNode
//{
//	int val;
//	ListNode next;
//	ListNode(int val)
//	{
//		this.val=val;
//	}
//}
public class Test13 
{

	public static void main(String[] args) 
	{
		ListNode p1=new ListNode(1);		
		ListNode p2=new ListNode(2);
		p1.next=p2;
		ListNode p3=new ListNode(3);
		p2.next=p3;
		ListNode p4=new ListNode(4);
		p3.next=p4;
		p4.next=null;
		ListNode p0=p1;
		while(p0!=null)
		{
			System.out.println(p0.val);
			p0=p0.next;
		}
		delete(null,p2);
		ListNode po=p1;
		while(po!=null)
		{
			System.out.println(po.val);
			po=po.next;
		}
		
	}
    public static void delete(ListNode head,ListNode deleted)
    {
    	if(head==null||deleted==null)
    		return;
    	if(head==deleted&&deleted.next==null)   		
    	{   		
    		head=null;
    		return;
    	}
        if(deleted.next!=null)
        {
        	deleted.val=deleted.next.val;
        	deleted.next=deleted.next.next;
        	return;
        }
        if(deleted.next==null)
        {
        	ListNode p = head;
        	while(p.next!=deleted)
        	{
        		p=p.next;
        	}
        	p.next=null;
        	return;
        }
    }
}
class DeleteNodeInO1{
	/**
	 * ��o(1)ʱ���� ɾ���ڵ㡣
	 * ��ȷ�Ͻڵ��Ƿ��ڸ������е����񽻸�������
	 * @param listNode
	 * @param delNode
	 */
	public void deleteNode(ListNode listNode, ListNode delNode){
		if(listNode == null || delNode == null){
			return ;
		}
		if(delNode.next != null){
			delNode.val = delNode.next.val;
			delNode.next = delNode.next.next;
		}else{
			if(listNode == delNode){
				listNode = null;
			}else {
				ListNode tmp = listNode ;
				while(tmp.next != delNode){
					tmp = tmp.next;
				}
				tmp.next = null;
			}
		}
	}
}